package com.ddf.datastructure.sort;

import java.util.Arrays;

/**
 * 冒泡排序
 *
 * 需要循环数组相邻的两个元素，如果逆序则交换两个元素，直到所有的相邻的元素都比较完成；
 * 第一趟循环能够确定最后一位的数组元素，下一次循环就会比上一次少循环一次，只要比剩余的几个元素就好，每次循环结束就会确定一个元素的位置；
 *
 * 循环一趟需要从数组的当前角标和下一个元素进行比较，然后角标后移，一直循环到最后一个元素的前一位，因为循环的时候每个元素都会和
 * 下一个元素进行比较，所以最后一个元素不需要再循环和他并不存在的下一位进行比较了；所以可以发现确定一个元素就需要循环数组的长度 - 1次，这一步不仅仅是优化，
 * 因为不这么去做不-1的话，最后一个元素怎么和它之后的元素比，会数组越界啊.......
 * 而需要确定所有的元素，就需要再外面嵌套一层再循环数组的长度次，用来完成所有元素的位置确定；
 * 冒泡排序的时间复杂度普遍说法为O(n²) ，但其实按照上面逻辑来看更能准确描述的应该是T(n)=(n*(n-1))，这个是毫无任何优化的情况下，-1是为了避免数组越界不得不-的啊，并没有
 * 考虑优化，冒泡排序根本不可能超过n²次，最差时间复杂度也就是O(n*(n-1))，当然好像也确实没看到这种表达方式，但是如果真的有两个常数双重for循环
 * 难道只能记为平方吗？毕竟都能存在mlog2，这种外层循环对内层循环进行解释；当然最优的情况下是O(n)这个是没有争议的
 *
 * 冒泡排序可以优化的两个点,影响非常大，第一点是不管任何数据都会极大减少循环次数
 * 1. 比较相邻两个元素一直到最后一个元素来进行换位的循环中，第一次循环只需要循环数组长度-1次，理由上面已经说了，确定好一个之后再继续往下循环，
 *      由于上面已经确定一个了，所以这一次只要循环数组长度-1-已确定元素个数就可以了，这会极大的减少循环次数
 * 2. 这个是在循环每个元素内容比较是否需要交换的时候，如果发生了交换就给一个标识赋值，而在循环语句外，发现这个标识如果值没有更改，说明没有发生交换，
 *      那么就可以认为数组已经是有序的，可以直接break外层循环,这种理想情况下，就会出现最佳情况的O(n)
 *
 *
 *
 *
 * @author dongfang.ding
 * @date 2019/6/26 15:01
 */
public class BubbleSort {

    public static void main(String[] args) {
        int[] arr = {20, 19, 18, 17, 16, 15, 14, 13};
        int[] sort = sort(arr);
        System.out.println("排序前： " + Arrays.toString(arr));
        System.out.println("排序后： " + Arrays.toString(sort));
    }

    public static int[] sort(int[] arr) {
        int[] dest = new int[arr.length];
        // 不改变原数组
        System.arraycopy(arr, 0, dest, 0, dest.length);
        int temp;
        int count = 0;
        // 在发生交换的时候会改变该值，在内循环结束时如果该值未改变，则说明没有发生交换，则可以说明数组已经有序了
        boolean swap = false;
        // 循环数组元素个长度，用来完成所有元素的最终位置的排序，内层循环一遍只可以确定一个元素；而由于确定元素位置是两两比较，
        // 两个元素只需要确定一个元素，最终那个元素的位置自然也是正确的，三个元素只需要两两比较替换两次，所以最终
        // 最外层完成所有元素的定位只需要数组长度 - 1即可
        for (int i = 0; i < dest.length - 1; i ++) {
            // i每增一次，就完成了一个元素的排序，则下一次的元素排序就少确定一次，因为没必要再和之前已经排好序的元素进行比较
            // 因为元素是从前往后确定的，所以j每次还是要初始为0，只是内层少循环已经确定过的元素个数次,这会极大减少循环次数，不减i也可以，多循环就是了
            for (int j = 0; j < dest.length - 1 - i; j ++) {
                count ++;
                if (dest[j] > dest[j + 1]) {
                    temp = dest[j];
                    dest[j] = dest[j + 1];
                    dest[j + 1] = temp;
                    swap = true;
                }
            }
            if (!swap) {
                break;
            } else {
                swap = false;
            }
        }
        System.out.println("共循环次数： " + count);
        return dest;
    }
}
